A Genetic Algorithm (GA)'s goal is to search and optimize. To find possible solutions to any given problem.
Route design:
Scheduling planner:
# Import libraries:
from IPython.display import HTML
import numpy as np
import plotly.express as px
import pandas as pd
import matplotlib.pyplot as plt
import plotly.graph_objects as go
subtract= lambda x: np.subtract(*x)
divide= lambda x: np.divide(*x)
A Genetic Algorithm (GA)'s goal is to search and optimize. To find possible solutions to any given problem.
Route design:
Scheduling planner:
Feature Selection:
Building graph structures:
$$ \text{Structure Learning of Bayesian Networks (DAG)} $$
Real life applications:
A notable real-life application of Genetic Algorithms (GA) lead to the creation of a very specific anthena by NASA:
An optimization problem consists of maximizing (or equivalently, minimizing) a function by choosing input values from within an allowed set and computing the value of the function. More generally, optimization focuses on finding "best possible values" of some objective function given a defined domain:
A search space within the optimization framework is the domain of the function to be optimized. Search spaces for objective functions are not always smooth, a few examples:
· Unimodal: This is the optimal search space, where gradients are smooth
· Needle in a Haystack: It can be easy to miss the peak
· Noisy: spaces with lots of variations can lead to local optima
· Deceptive: searching with gradient type algorithm can be deceptive
In general, Genetic Algorithms (GA) won't be able to solve every problem. No free lunch theorem (NFL): There is no single algorithm that is superior at solving problems, to all other algorithms in general. Evolutionary algorithms are efficient at solving discontinuous, non-differentiable, multimodal problems, with noise and unconventional search spaces. On the contrary, its effectiveness decreases when facing simpler problems for which specific algorithms have been developed in their resolution.
Poner grafica con publicaciones por año!
The solution space, in general, can be different from the search space. This is very common in Evolutionary computation where we work with a codification of the solution as symbols or programs in the search space. Therefore, codification and search space setup, will play a key role in the success of the algorithm. If the search space is larger than the solution space, we will find invalid solutions. If the solution space is larger than the search space, it might happen that we don't find the optimal solution.
Redundancy:
Different encodings can code the same solution. When this happens, there are different symbols for the same solution so it is possible to find it more quickly (has been empirically proven).
Ambiguity:
Different solutions can be encoded by the same symbols.
Exploitation (local search):
Consists of sampling a limited (but already identified as promising) region of the search space with the hope of improving an existing solution. This operation, then, tries to intensify (refine) the search in the neighbourhood of the existing solution.
Exploration (global search):
Consists of sampling a much larger portion of the search space with the hope of finding other promising solutions that are yet to be refined. This operation, tries to diversify the search in order to avoid local optimums.
A good search algorithm will have to keep a balance in order to explore a large search space at the beginning and narrow down the search in final iterations.
The trade-off criteria for deciding whether to use a heuristic for solving a given problem include the following:
Performance: Some heuristics converge faster than others while some are only marginally quicker than classic methods.
They are increasingly used in intermediate and large search space. In optimization complexity terms, they are often used to solve NP Problems and large combinatorial problems in P too.
</p>
</p>
A Genetic Algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). It is based on neo-Darwinism paradigm: "survival of the fittest", where most of the history of life can be completely justified by physical processes, populations and species. These processes are:
Reproduction
It involves the transfer of the genetic code of each individual to their offspring.
Mutation
Due to errors in replication during the genetic information transfer process are unavoidable. In addition, mutation is necessary to include diversity in the species.
Competition (Selection)
It is a consequence of population growth within a finite physical space where there is no space or energy for everyone. Selection is the result of the reproduction of the species in a competitive environment: only the individuals that are more adapated to the environment, survive (i.e. the fittest).
Population
The set of points in the search space or individuals (possible solutions to the problem) with which a GA works at a given moment in the evolution process.
Chromosomes (individual)
A chromosome is usually identified as an individual in Genetic Algorithms, although in nature, an individual consists of several chromosomes. Individuals and species can be seen as a duality of their genetic code, the genotype, and their way of expressing themselves with respect to the physical world, the phenotype. The genotype offers the possibility of storing the accumulated experience, acquired from historical information.
In summary:
Genotype
The set of genes representing the chromosome (Search space).
Phenotype
The actual physical representation of the chromosome (Solution space).
Genes
Set of parameters that represent the individuals that make up a population. Each gene represents a position in the chain.
Allele
Possible values of each gene (symbols). The number of alleles is equal to the cardinality of the alphabet used (m).
As part of Evolutionary Algorithms, GA use mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function). Evolution of the population then takes place after the repeated application of the above operators.
Problem statement:
The goal of the game is to find the right operators (+,-,*,$\div$) to place them between the numbers in order for to achieve target value (or as close as possible).
Note: To keep it simple the operations are completed in sequencial order (there is no BODMAS order)
$$ 75\hspace{0.3cm} \_ \hspace{0.3cm}
3\hspace{0.3cm} \_ \hspace{0.3cm}
1\hspace{0.3cm} \_ \hspace{0.3cm}
4\hspace{0.3cm} \_ \hspace{0.3cm}
50\hspace{0.3cm} \_ \hspace{0.3cm}
6\hspace{0.3cm} \_ \hspace{0.3cm}
12\hspace{0.3cm} \_ \hspace{0.3cm}
8\hspace{0.3cm} = \hspace{0.3cm}
target$$
In order to build genetic chains, an encoding of the solution onto the search space must be provided. A careful choice, will help the algorithm converge to the right solution and yield faster performance.
A population is initialized randomly in the first iteration (generation) of every simulation. The hyperparameter $P$, size of population has to be chosen before execution while $S$, size of individuals is fixed by the paramaters of the problem we are trying to optimize (in this case the numbers):
At every timestep (generation), the population has to be evaluated through a $Fitness$ function. This $Fitness$ function will provide a score for each individual, indicating if the individual is a good candidate for the overall solution or not. Keep in mind that this function will me evaluated $PxG$ times, where $P$ is the size of population and $G$, the number of generations. So a Fitness function has to be fast and efficient.
5.4. Selection
Some individuals are selected to create new generations of individuals. The idea is for individuals with greater level of adaptation (i.e. fitness) to be chosen with higher probability, and therefore passing on genetic information to their offsprings.
Once the mating individuals are chosen, it remains to define how they will reproduce to develop new individuals. This is the most valuable operator in the Genetic Algorithm's architecture. It will determine the success of the search problem.
New generations of individuals are generated from the selected individuals,by choosing one crossover point at random. The goal is to preserve large building blocks from fittest individuals in current generation.
$$\text{Single Point Crossover}$$
5.4.2. Uniform crossover
It has been proven in the literature that adding more crossover points helps the algorithms uptil a certain point $\text{(DeJong, 75 )}$. In general, more than two crossover points reduces performance. The reason for this is that the building blocks will of course be disrupted more often, however there is a tradeoff, it will help adding diversity and exploring further the search space.
</p>
5.6. Mutation
The mutation operator modifies the gene of the individuals stochastically. The goal of this operator is to increase the search space in which the algorithm is looking for the solution. Use of mutation operators are usually kept below p=0.05, as they introduce randomness to the algorithm.
</p>
Once new individuals have been generated, it remains to see, which ones are kept in the population. In general, the population size is invariant with time. Therefore, some individuals, will have to be replaced in order to keep the fittest individuals with higher probability.
An elitist replacement operator is completely deterministic. It chooses only the individuals with the highest fitness among previous and current generation of individuals, to create next iteration’s population. The rest are eliminated.
</p>
A simple reduction replacement operator is stochastic. It chooses individuals with the lower fitness to be replaced with higher probability, among previous and current generation of individuals.
</p>
</p>
Regarding convergence, there are various metrics that study convergence of Genetic Algorithms $\text{[5]}$. Two common metrics are:
$$ \textrm{Offline measure}\hspace{0.5cm} m^{*}(T)=\dfrac{1}{T}\sum_{t=1}^{T}(f(I^{*}(t)) $$Where $ f(I^{*}(t))$ is the fitness of the fittest individual at generation t. Therefore, offline measurement can be interpreted as a progress indicator. After a number of generations, this measurement can be near the optima or not, however the velocity of when this happens indicates the ability of the algorithm to establish itself near the solution. It can serve the purpose of being used as a stopping criteria (i.e. when difference between generations is close).
$$ \textrm{Online measure}\hspace{0.7cm} m(T)=\dfrac{1}{T}\sum_{t=1}^{T}F(t) $$
Online measurement is defined as the mean, for the objective function, till evaluation. Where F(t) is the mean of fitness of all individuals available at generation t.
class GeneticAlgorithm:
"""
Attributes
----------
parameters: list
fixed parameters for optimization
population_size: int
number of individuals in each generation
population_history: list
tracking of populations' evolution
fitness_history: list
tracking of fitness' evolution
"""
decode={0:np.sum,
1:np.prod,
2:subtract,
3:divide}
decode_str={0:'+',
1:'*',
2:'-',
3:'/'}
def __init__(self,
parameters:list,
population_size:int,
target:float):
self.parameters=parameters
self.population_size=population_size
self.population_history=[]
self.fitness_history=[]
self.target=target
@property
def population(self):
"""Returns population for current iteration."""
return self._population
@population.setter
def population(self,x):
"""Sets population and calculates fitness for new population."""
self._population=x
self.population_history.append(x)
self.fitness,self.values=self.get_fitness()
@property
def fitness(self):
"""Return fitness for current iteration."""
return self._fitness
@fitness.setter
def fitness(self,x):
"""Set fitness for new population."""
self._fitness=x
self.fitness_history.append(x)
def get_fitness(self,
population:np.array = None)->tuple:
"""Calculate fitness and value for new population.
Parameters
----------
population: array
individuals for which to calculate fitness
Returns
-------
fitness: array
fitness score
value: array
objective function values
"""
if population is None:
population=self.population
fitness=[]
values=[]
for individual in population:
total=self.parameters[0]
for param,gene in enumerate(individual):
total=self.decode[gene](np.array([total,
self.parameters[param+1]]))
values.append(total)
fitness.append(np.round(abs(self.target -total),2))
return np.array(fitness),np.array(values)
def selection(self,
num_parents:int=4,
epsilon:float=1e-5,
method:str='proportional',
replacement:bool=False)->np.array:
"""Apply selection operator.
Parameters
----------
method: str
choose between 'proportional' - invariant to scale
and 'smooth' - invariant to scale and translation
"""
assert num_parents%2==0
if method=='proportional':
crossover_probability=1/(self.fitness+epsilon)
crossover_probability/=np.sum(crossover_probability)
individuals_to_cross=np.random.choice(range(len(crossover_probability)),
size=num_parents,
replacement=False,
p=crossover_probability)
elif method=='smoothed':
crossover_probability=(1+np.argsort(self.fitness))\
/(len(self.fitness)*(len(self.fitness)+1)/2)
individuals_to_cross=np.random.choice(range(len(crossover_probability)),
size=num_parents,
replace=replacement,
p=crossover_probability)
return individuals_to_cross
def crossover(self,
parents:list,
method:str = 'uniform')->np.array:
"""Apply crossover operator.
Parameters
----------
parents: list(int)
index of individuals to crossover
Returns
-------
children: np.array
new individuals (offspring)
"""
children=[]
if method=='uniform':
for parent1_id,parent2_id in zip(parents[::2],parents[1::2]):
parent1=self.population[parent1_id]
parent2=self.population[parent2_id]
crossover_mask=np.random.randint(2,
size=self.population.shape[1])
mask1,mask2=[np.where(i==crossover_mask)[0] for i in (0,1)]
child1=np.zeros(self.population.shape[1])
child2=np.zeros(self.population.shape[1])
child1[mask1]=parent1[mask1]
child1[mask2]=parent2[mask2]
child2[mask2]=parent1[mask2]
child2[mask1]=parent2[mask1]
children.append(np.vstack([child1,child2]))
children = np.array(children).reshape(len(parents),
self.population.shape[1])
return children
def mutation(self,
subpopulation:np.array,
probability_mutation:float=0.05,
method='gene')->np.array:
"""Apply mutation operator.
Parameters
----------
probability_mutation: float
probability of mutation
Returns
-------
subpopulation: np.array
Mutated population
"""
if method=='gene':
for individual in subpopulation:
mutation_idx=np.where(np.random.uniform(
size=len(self.parameters)-1)>=1-probability_mutation)[0]
if len(mutation_idx)>0:
individual[mutation_idx]=np.random.randint(
np.max(list(self.decode)),size=len(mutation_idx))
return subpopulation
def replacement(self,
subpopulation:np.array,
method='SteadyState')->np.array:
"""Apply replacement operator.
Parameters
----------
method: str
Choose among 'SteadyState' - replace a fixed % of old population
or 'Elitist' - keep fittest from old and new population
"""
if method=='elitist':
newfitness=self.get_fitness(population=subpopulation)[0]
allpopulation=np.vstack([self.population,subpopulation])
allfitness=np.hstack([self.fitness,newfitness])
best_fitted=np.argsort(allfitness)[:self.population.shape[0]]
newpopulation=allpopulation[best_fitted]
return newpopulation
def search(self,iterations=100,
simulations=20,
p_mutation=0.05,
num_parents=4,
max_gene_convergence=0.95,
selection_method='smoothed',
crossover_method='uniform',
mutation_method='gene',
replacement_method='elitist')->None:
"""Search and optimize fitness function."""
fittest_fitness=[]
fittest_individual=[]
best_fitness=[]
global_best_fitness=1000
for simulation in range(0,simulations):
for iteration in range(0,iterations):
if iteration==0:
#Initialize population and calculate fitness:
self.population=np.random.randint(4,
size=(self.population_size,len(self.parameters)-1))
else:
#Selection
individuals_to_cross = self.selection(num_parents,
method=selection_method)
#Crossover
children = self.crossover(parents=individuals_to_cross,
method=crossover_method)
#Mutation
children = self.mutation(children,
probability_mutation=p_mutation,
method=mutation_method)
#Replacement
newpopulation = self.replacement(subpopulation=children,
method=replacement_method)
#Set new population (and calculate new fitness)
self.population=newpopulation
#Best fitness in iteration:
best_fitness_iteration=np.min(self.fitness)
fittest_fitness.append([simulation,
iteration,
best_fitness_iteration])
fittest_individual.append([simulation,
iteration,
self.population[np.argmin(self.fitness)]])
#Convergence (if max_gene_convergence, break this simulation)
sorted_population= np.sort(self.population,axis=0)
different_values=(sorted_population[1:,:] !=
sorted_population[:-1,:]).sum(axis=0)+1
convergence=np.mean(different_values==1)
if convergence>=max_gene_convergence:
break
#Updates minimum fitness value if it decreases
if(best_fitness_iteration<global_best_fitness):
global_best_fitness = best_fitness_iteration
best_fitness.append([simulation,
iteration,
best_fitness_iteration])
if best_fitness_iteration==0:
return
self.fittest_fitness=fittest_fitness
self.fittest_individual=fittest_individual
self.best_fitness=best_fitness
return
def result_plot(self,interactive=False)->plt.plot:
"""Plot best fitness of every iteration."""
best_fitness_df=pd.DataFrame(self.fittest_fitness,
columns=['simulation','iteration','bestfitness'])
all_individual_df=pd.DataFrame(self.fittest_individual,
columns=['simulation','iteration','individual'])
absolute_best=all_individual_df[(all_individual_df.simulation==
self.best_fitness[-1][0])&
(all_individual_df.iteration==
self.best_fitness[-1][1])]
display(absolute_best)
absolute_best_fitness,absolute_best_values=self.get_fitness(
absolute_best.individual.values)
print(f'Fitness:{absolute_best_fitness[0]} \t Value: {absolute_best_values[0]}')
if interactive:
y_max = best_fitness_df.bestfitness.max(),
y_min = best_fitness_df.bestfitness.min()
fig = px.line(best_fitness_df,
x='iteration',
y='bestfitness',
animation_frame="simulation",
animation_group="iteration",
range_x=[0,100],
range_y=[y_min,y_max],
title='Best fitness')
else:
fig=px.line(best_fitness_df,
x='iteration',
y='bestfitness',
color='simulation')
fig.show()
def convergence_plot(self,interactive=False)->plt.plot:
""" Plot convergence metrics.
Display plots for offline measure & online measure
as seen in ([1] DeJong K., 1975)
"""
def offline_measure(df):
return pd.Series(df['fitness'].cumsum().values/
(df['iteration'].values+1))
def online_measure(df):
return pd.Series(df['mean_fitness'].cumsum().values/
(df['iteration'].values+1))
return NotImplementedError
def __str__(self):
"""String representation of last population stored."""
text=[]
for i,individual in enumerate(self.population):
total=str(self.parameters[0])
for param,gene in enumerate(individual):
total+=f'{self.decode_str[gene]}{self.parameters[param+1]}'
total+=f'={round(self.values[i],2)} \t - fitness:{round(self.fitness[i],2)}'
text.append(total)
return ", \n".join(text)
GA=GeneticAlgorithm(parameters=[75, 3, 1, 4, 50, 6, 12, 8],population_size=10,target=852)
GA.search(simulations=20)
GA.result_plot()
| simulation | iteration | individual | |
|---|---|---|---|
| 1406 | 17 | 30 | [1.0, 1.0, 1.0, 2.0, 0.0, 2.0, 0.0] |
Fitness:0 Value: 852
GA.result_plot(interactive=True)
| simulation | iteration | individual | |
|---|---|---|---|
| 1406 | 17 | 30 | [1.0, 1.0, 1.0, 2.0, 0.0, 2.0, 0.0] |
Fitness:0 Value: 852
With minimal changes, a continuous search space example:
class GeneticAlgorithm:
"""
Attributes
----------
parameters: list
fixed parameters for optimization
population_size: int
number of individuals in each generation
population_history: list
tracking of populations' evolution
fitness_history: list
tracking of fitness' evolution
minimum_values: list
lower bound value for every gene
[lower_bound_gene1, ..., lower_bound_geneN]
maximum_values: list
upper bound value for every gene
[upper_bound_gene1, ..., upper_bound_geneN]
"""
def __init__(self,
parameters:list,
population_size:int,
minimum_values:list,
maximum_values:list):
self.parameters=parameters
self.population_size=population_size
self.population_history=[]
self.fitness_history=[]
self.minimum_values=minimum_values
self.maximum_values=maximum_values
@property
def population(self):
"""Return population for current iteration."""
return self._population
@population.setter
def population(self,x):
"""Set population and calculates fitness for new population.
"""
self._population=x
self.population_history.append(x)
self.fitness=self.get_fitness()
@property
def fitness(self):
"""Return fitness for current iteration."""
return self._fitness
@fitness.setter
def fitness(self,x):
"""Set fitness for new population."""
self._fitness=x
self.fitness_history.append(x)
def get_fitness(self,
population:np.array=None)->np.array:
"""Calculate fitness and value for new population.
Parameters:
----------
population: array
individuals for which to calculate fitness
Returns
-------
fitness: array
fitness score
"""
if population is None:
population=self.population
fitness=[]
for individual in population:
# TODO:
# Fill with custom fitness function
raise NotImplementedError
return np.array(fitness)
def selection(self,
num_parents:int=4,
epsilon:float=1e-5,
method:str='proportional',
replacement:bool=False)->np.array:
""" Apply selection operator.
Parameters:
----------
num_parents: int
number of parents to include in mating pool.
Also number of children to output.
method: str
choose between 'proportional' - invariant to scale
and 'smooth' - invariant to scale and translation
epsilon: float
constant
replacement: bool, optional
optional to choose with or without replacement
Returns
-------
individuals_to_cross: np.array
index of individuals to cross
"""
assert num_parents%2==0
if method=='proportional':
crossover_probability=self.fitness/np.sum(crossover_probability)
individuals_to_cross=np.random.choice(range(len(crossover_probability)),
size=num_parents,
replacement=False,
p=crossover_probability)
elif method=='smoothed':
#Highest fitness individual, gets chosen more often:
crossover_probability=(len(self.fitness)-(np.argsort(-self.fitness)))\
/(len(self.fitness)*(len(self.fitness)+1)/2)
individuals_to_cross=np.random.choice(range(len(crossover_probability)),
size=num_parents,
replace=replacement,
p=crossover_probability)
return individuals_to_cross
def crossover(self,parents:list,method:str='BLX')->np.array:
""" Apply crossover operator.
Parameters
----------
parents: list
index of individuals to crossover
method: str
crossover operator.
Options - 'BLX' (blend crossover,
within parents interval)
Returns
-------
new individuals (offspring)
"""
children=[]
if method=='BLX':
for parent1_id,parent2_id in zip(parents[::2],parents[1::2]):
parent1=self.population[parent1_id]
parent2=self.population[parent2_id]
stacked=np.vstack([parent1,parent2])
min_ab=np.min(stacked,axis=0)
max_ab=np.max(stacked,axis=0)
child1=np.random.uniform(min_ab,max_ab)
child2=max_ab-(child1-min_ab)
children.append(np.vstack([child1,child2]))
children = np.array(children).reshape(len(parents),
self.population.shape[1])
return children
def mutation(self, subpopulation:np.array,
probability_mutation:float = 0.05,
method: str = 'gene')->np.array:
"""Apply mutation operator.
Parameters
----------
probability_mutation: float
probability of mutation
Returns
-------
subpopulation: np.array
population with mutations
"""
if method=='gene':
for individual in subpopulation:
mutation_idx=np.where(np.random.uniform(
size=self.population.shape[1])>=1-probability_mutation)[0]
if len(mutation_idx)>0:
individual[mutation_idx]=np.random.uniform(
self.minimum_values[mutation_idx],
self.maximum_values[mutation_idx])
return subpopulation
def replacement(self,
subpopulation:np.array,
method='SteadyState')->np.array:
"""Apply replacement operator.
Parameters
----------
subpopulation: np.array
subsample of population.
method: str
Choose 'SteadyState' - replace a fixed % of old population
or 'Elitist' - keep fittest from old and new population
"""
if method=='elitist':
newfitness=self.get_fitness(population=subpopulation)[0]
allpopulation=np.vstack([self.population,
subpopulation])
allfitness=np.hstack([self.fitness,
newfitness])
best_fitted=np.argsort(-allfitness)[:self.population.shape[0]]
newpopulation=allpopulation[best_fitted]
elif method=='SteadyState':
raise NotImplementedError
return newpopulation
def search(self,
iterations: int = 100,
simulations:int = 20,
p_mutation:float = 0.05,
num_parents:int = 4,
max_gene_convergence:float = 0.95,
selection_method:str = 'smoothed',
crossover_method:str = 'BLX',
mutation_method:str = 'gene',
replacement_method:str = 'elitist')->None:
"""Search and optimize fitness function.
Parameters
----------
iterations: int, optional
number of maximum generations for a
given simulation
simulations: int, optional
number of times to initialize GA
p_mutation: float, optional
probability of an individual mutating
num_parents: int, optional
number of parents to include in a
mating pool
max_gene_convergence: float, optional
stopping criteria for generation
selection_method: str, optional
selection operator
Options - 'smoothed', 'proportional'
crossover_method: str, optional
crossover operator. Options - 'BLX'
mutation_method: str, optional
mutation operator. Options - 'gene'
replacement_method: str, optional
replacement operator.
Options - 'elitist', 'SteadyState'
Returns
-------
population_history:np.array
history of populations' evolution
fitness_history:np.array
history of fitness' evolution
"""
fittest_fitness=[]
fittest_individual=[]
best_fitness=[]
global_best_fitness=-100000
self.simulations=simulations
self.iterations=iterations
for simulation in range(0,simulations):
for iteration in range(0,iterations):
if iteration==0:
#Initialize population and calculate fitness:
self.population=np.random.uniform(self.minimum_values,
self.maximum_values,
size=(self.population_size,
len(self.minimum_values)))
else:
#Selection
individuals_to_cross = self.selection(num_parents,
method=selection_method)
#Crossover
children = self.crossover(parents=individuals_to_cross,
method=crossover_method)
#Mutation
children = self.mutation(children,
probability_mutation=p_mutation,
method=mutation_method)
#Replacement
newpopulation = self.replacement(subpopulation=children,
method=replacement_method)
#Set new population (and calculate new fitness)
self.population=newpopulation
#Best fitness in iteration, choose Max or Min:
best_fitness_iteration=np.max(self.fitness)
fittest_fitness.append([simulation,
iteration,
best_fitness_iteration])
fittest_individual.append([simulation,
iteration,
self.population[np.argmax(self.fitness)]])
#Convergence (if max_gene_convergence, break this simulation)
sorted_population= np.sort(self.population,axis=0)
different_values=(sorted_population[1:,:] != sorted_population[:-1,:]).sum(axis=0)+1
convergence=np.mean(different_values==1)
if convergence>=max_gene_convergence:
break
#Updates max fitness value if it increases
if(best_fitness_iteration>global_best_fitness):
global_best_fitness = best_fitness_iteration
best_fitness.append([simulation,
iteration,
best_fitness_iteration])
self.fittest_fitness=fittest_fitness
self.fittest_individual=fittest_individual
self.best_fitness=best_fitness
return self.population_history,self.fitness_history
def get_best_parameters(self):
"""Retrieve best parameters found."""
best_sim,best_it,best_fit=self.best_fitness[-1]
best_individual_array = np.array(self.fittest_individual)
best_individual_array = best_individual_array.reshape(self.simulations,
self.iterations,
-1)
best_individual = best_individual_per_it[best_sim][best_it][-1]
return best_individual
def result_plot(self,
interactive:bool = False)->plt.plot:
"""Plot best fitness of every iteration.
Parameters
----------
interactive: bool
choose if plot is interactive or not
"""
best_fitness_df=pd.DataFrame(self.fittest_fitness,
columns=['simulation','iteration','bestfitness'])
all_individual_df=pd.DataFrame(self.fittest_individual,
columns=['simulation','iteration','individual'])
absolute_best=all_individual_df[(all_individual_df.simulation==
self.best_fitness[-1][0])&
(all_individual_df.iteration==
self.best_fitness[-1][1])]
display(absolute_best)
absolute_best_fitness=self.get_fitness(
absolute_best.individual.values)
print(f'Fitness:{absolute_best_fitness[0]}')
if interactive:
y_max = best_fitness_df.bestfitness.max()
y_min = best_fitness_df.bestfitness.min()
fig=px.line(best_fitness_df,
x='iteration',
y='bestfitness',
animation_frame="simulation",
animation_group="iteration",
range_x=[0,100],
range_y=[y_min,y_max],
title='Best fitness')
else:
fig=px.line(best_fitness_df,
x='iteration',
y='bestfitness',
color='simulation')
fig.show()
def convergence_plot(self,
interactive:bool = False)->plt.plot:
""" Plot convergence metrics.
Display plots for offline measure & online measure
as seen in ([1] DeJong K., 1975)
Parameters
----------
interactive: bool
choose if plot is interactive or not
"""
def offline_measure(df):
return pd.Series(df['fitness'].cumsum().values/
(df['iteration'].values+1))
def online_measure(df):
return pd.Series(df['mean_fitness'].cumsum().values/
(df['iteration'].values+1))
fittest_fitness_df=pd.DataFrame(self.fittest_fitness,
columns=['simulation',
'iteration',
'fitness'])
offline_measures=fittest_fitness_df.groupby('simulation')\
.apply(lambda x: offline_measure(x))
offline_measures=pd.pivot_table(offline_measures,index='simulation')\
.stack().reset_index()\
.rename(columns={'level_1':'iteration',0:'m*'})
offline_measures['iteration']=fittest_fitness_df['iteration']
fig=px.line(offline_measures,
x='iteration',
y='m*',
title='Offline measure',
color='simulation')
fig.show()
fittest_fitness_df['mean_fitness']=np.mean(self.fitness_history,
axis=1)
online_measures=fittest_fitness_df.groupby('simulation')\
.apply(lambda x: online_measure(x))
online_measures=pd.pivot_table(online_measures,
index='simulation')\
.stack().reset_index()\
.rename(columns={'level_1':'iteration',
0:'m'})
online_measures['iteration']=fittest_fitness_df['iteration']
fig=px.line(online_measures,
x='iteration',
y='m',
title='Online measure',
color='simulation')
fig.show()
if interactive:
# Create figure
fig = go.Figure()
# Add traces, one for each slider step
for step in set(online_measures['simulation']):
fig.add_trace(
go.Scatter(
visible=False,
line=dict(color="#00CED1", width=3),
name="m - Online measure ",
x=online_measures.loc[online_measures['simulation']==step,
'iteration'],
y=online_measures.loc[online_measures['simulation']==step,
'm']))
fig.add_trace(
go.Scatter(
visible=False,
line=dict(color="#008888", width=3),
name="m* - Offline measure ",
x=offline_measures.loc[offline_measures['simulation']==step,
'iteration'],
y=offline_measures.loc[offline_measures['simulation']==step,
'm*']))
# Make 1st trace visible
fig.data[1].visible = True
# Create and add slider
steps = []
for i in range(0,len(fig.data),2):
step = dict(
method="update",
args=[{"visible": [False] * len(fig.data)},
{"title": f"Offline-online measure - Simulation {i+1}"}])
step["args"][0]["visible"][i] = True # Toggle i'th trace to "visible"
step["args"][0]["visible"][i+1] = True
steps.append(step)
sliders = [dict(
active=10,
currentvalue={"prefix": "Simulation: "},
pad={"t": 50},
steps=steps
)]
fig.update_layout(
sliders=sliders
)
fig.show()
return
def __str__(self):
"""String representation of last population stored."""
text=[]
for i,individual in enumerate(self.population):
total=f'param1={individual[0]},param2={individual[1]},param3=[{individual[2]}]'
total+=f'\t - fitness:{round(self.fitness[i],2)}'
text.append(total)
return ", \n".join(text)
[1] Leardi, Riccardo, R. Boggia, and M. Terrile. Genetic algorithms as a strategy for feature selection. Journal of chemometrics 6, no. 5 (1992): 267-281.
[2] Barrios, Dolores, Alberto Carrascal, Daniel Manrique, and Juan Rios. Cooperative binary-real coded genetic algorithms for generating and adapting artificial neural networks. Neural Computing & Applications 12, no. 2 (2003): 49-60.
[3] Larranaga, Pedro, Mikel Poza, Yosu Yurramendi, Roberto H. Murga, and Cindy M. H. Kuijpers. Structure learning of Bayesian networks by genetic algorithms: A performance analysis of control parameters. IEEE transactions on pattern analysis and machine intelligence 18, no. 9 (1996): 912-926.
[4] Hornby, Gregory, Al Globus, Derek Linden, and Jason Lohn. Automated antenna design with evolutionary algorithms. In Space 2006, p. 7242. 2006.
[5] DeJong, K.The Analysis and behaviour of a Class of Genetic Adapative Systems. PhD Thesis, University of Michigan, 1975.